LeetCode 16、最接近三数之和

一、题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最接近的三数之和(16)：https://leetcode-cn.com/problems/3sum-closest/submissions/
class Solution {
    public int threeSumClosest(int[] nums, int target) {

        // 题目假定每组输入只存在恰好一个解，所以不需要处理边界情况
        int ans = nums[0] + nums[1] + nums[2];

        // 先将数组进行排序操作，从小到大
        Arrays.sort(nums); 

        // 开始遍历整个数组
        // 在遍历的过程中，观察设置的三个位置的元素之后的大小
        // num[i] 为从左到右观察过去的元素
        // left 为从 i 到 len - 1 的元素
        // right 为从 len - 1 向左移动到 i 的元素
        for (int i = 0; i < nums.length ; i++) {

            // left 为从 i 到 len - 1 的元素，向右移动
            int left = i + 1;

            // right 为从 len - 1 向左移动到 i 的元素，向左移动
            int right = nums.length - 1;

            // left 和 right 不断的向内移动
            while(left < right){
                
                // 计算这三者之和
                int sum = nums[i] + nums[left] + nums[right];

                // 寻找出更接近于 target 的那个和
                if(Math.abs(target - sum) < Math.abs(target - ans)){
                     ans = sum;
                }
                   
                // 如果三者之和小于 target ，那么说明需要找更大的数
                if (sum < target){
                    // left 向右移动
                    left++;

                // 如果三者之和大于 target ，那么说明需要找更小的数
                }else if (sum > target) {
                    // right 向左移动
                    right--;
                }else{
                    return ans;
                }
            }
        }     
        // 返回结果   
        return ans;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最接近的三数之和(16)：https://leetcode-cn.com/problems/3sum-closest/submissions/
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        // 题目假定每组输入只存在恰好一个解，所以不需要处理边界情况
        int ans = nums[0] + nums[1] + nums[2];

        // 先将数组进行排序操作，从小到大
        sort(nums.begin(), nums.end());

        // 开始遍历整个数组
        // 在遍历的过程中，观察设置的三个位置的元素之后的大小
        // num[i] 为从左到右观察过去的元素
        // left 为从 i 到 len - 1 的元素
        // right 为从 len - 1 向左移动到 i 的元素
        for (int i = 0; i < nums.size() ; i++) {

            // left 为从 i 到 len - 1 的元素，向右移动
            int left = i + 1;

            // right 为从 len - 1 向左移动到 i 的元素，向左移动
            int right = nums.size() - 1;

            // left 和 right 不断的向内移动
            while(left < right){
                
                // 计算这三者之和
                int sum = nums[i] + nums[left] + nums[right];

                // 寻找出更接近于 target 的那个和
                if(abs(target - sum) < abs(target - ans)){
                     ans = sum;
                }
                   
                // 如果三者之和小于 target ，那么说明需要找更大的数
                if (sum < target){
                    // left 向右移动
                    left++;

                // 如果三者之和大于 target ，那么说明需要找更小的数
                }else if (sum > target) {
                    // right 向左移动
                    right--;
                }else{
                    return ans;
                }
            }
        }     
        // 返回结果   
        return ans;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 最接近的三数之和(16)：https://leetcode-cn.com/problems/3sum-closest/submissions/
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 题目假定每组输入只存在恰好一个解，所以不需要处理边界情况
        ans = nums[0] + nums[1] + nums[2]

        # 先将数组进行排序操作，从小到大
        nums.sort()

        # 开始遍历整个数组
        # 在遍历的过程中，观察设置的三个位置的元素之后的大小
        # num[i] 为从左到右观察过去的元素
        # left 为从 i 到 len - 1 的元素
        # right 为从 len - 1 向左移动到 i 的元素
        for i in range(len(nums)) :

            # left 为从 i 到 len - 1 的元素，向右移动
            left = i + 1

            # right 为从 len - 1 向左移动到 i 的元素，向左移动
            right = len(nums) - 1

            # left 和 right 不断的向内移动
            while left < right :
                
                # 计算这三者之和
                sum = nums[i] + nums[left] + nums[right]

                # 寻找出更接近于 target 的那个和
                if abs(target - sum) < abs(target - ans) : 
                    ans = sum
                
                   
                # 如果三者之和小于 target ，那么说明需要找更大的数
                if sum < target :
                    # left 向右移动
                    left += 1

                # 如果三者之和大于 target ，那么说明需要找更小的数
                elif sum > target : 
                    # right 向左移动
                    right -= 1
                else : 
                    return ans
       
        # 返回结果   
        return ans

四、复杂度分析

时间复杂度：O(N^2)，其中 N 是数组 nums 的长度。

空间复杂度：O(logN)。